googologywikiaorg-20200223-history
Forum:Holy crap!
It seems that the fastest growing computable functions that we can define are by explicit diagonalization out of strong theory like ZFC+I0, e.g. take f(n) to be the largest number of steps that it takes a Turing machine to halt, that can be proven to halt in ZFC+I0 using at most n steps. It seems like we can get arbitrarily strong this way by choosing stronger and stronger theories. Still, there is some interest in finding "natural" fast growing computable functions, where by "natural" I mean not obviously diagonalizing out of a particular theory or calculus. As of now, I believe the fastest growing "natural" computable functions, at least in terms of lower bounds, come from Friedman's "Finite Promise Games", which Friedman states outgrow all provably recursive functions in SMAH (ZFC + "there exists a strongly k-Mahlo cardinal" for all k). Other contenders include witness functions from Friedman's "Finite Trees..." and "Finite Functions..." papers, where the functions derive from statements that are not provable in ZFC + "there exists a k-subtle cardinal" for all k; it seems reasonable that the witness functions will then dominate all provably recursive functions in ZFC + "there exists a k-subtle cardinal", but nowhere does Freidman state this is the case in his papers. Another contender is the obvious fast-growing function derived from Laver tables, which was proven to exist using rank-into-rank cardinals, but here we are on even shakier ground since it could well be that it could be proven in some weak theory. Well, I just ran across a post by Friedman where he defines three functions, two of which dominate all functions provably recursive in SRP (ZFC + Stationary Ramsey Property), and one of which dominates all functions provably recursive in HUGE (ZFC + "there exists an n-huge cardinal" for all n). Huge cardinals are really huge! Strongly Mahlo cardinals are near the bottom of the large cardinal hierarchy; subtle cardinals are higher up but still relatively low. SRP is also not that high, higher than subtle I think but below measurable, which is considered the midpoint of the hierarchy, sort of. Huge is near the top. So this is a pretty big leap. Also, Friedman talks about a version for I3/I2, which is at the top, below just I0/I1. (Unfortunately he doesn't describe this version.) The post is here: http://www.cs.nyu.edu/pipermail/fom/2010-January/014282.html I had a little trouble deciphering it; I'm not sure what he means by concatenation, and some of the statements start of with "if" but have no "then". :( Hopefully we can figure this out. Deedlit11 (talk) 03:18, September 13, 2015 (UTC) :The concatenation operation seems pretty clear. I have explained it more clearly in greedy clique sequence. The "if" statements worry me. It looks like the missing second halves of those sentences are what distinguish the first and second definitions. -- ve 06:31, September 13, 2015 (UTC) :Aha. Correction here: http://www.cs.nyu.edu/pipermail/fom/2010-January/014285.html -- ve 06:49, September 13, 2015 (UTC) :Friedman mentions a W(k) function in his original uncorrected post. http://www.cs.nyu.edu/pipermail/fom/2010-January/014282.html Anyone know how it compares to the three aforementioned functions? --Ixfd64 (talk) 18:25, October 14, 2015 (UTC) ::If I understand correctly, then W(k) you mention isn't any single function - Friedman wants to define a witness function for each theorem in general. This is a single placeholder for three functions mentioned in theorem 8. LittlePeng9 (talk) 18:31, October 14, 2015 (UTC)